The phenomenal success of TCP, and, in particular, the congestion control protocol of Jacobson, has played a central role in the unprecedented growth of the Internet. These protocols have scaled gracefully all the way from a small-scale research network to today's Internet with the tens of millions of end nodes and links, the highly heterogeneous composition and growth, and the very diverse collection of users and applications. This remarkable success has attracted much theoretical study, with a view to designing next generation protocols. This activity has so far been centered around continuous time algorithms, which do not have time-efficiency guarantees.
Conventionally, convex programs can be employed to find equilibrium solution, but are very slow and/or resource intensive. On the other hand, combinatorial optimization can be more efficient process under certain circumstances. A central theme within combinatorial optimization was the design of combinatorial algorithms for solving specific classes of linear programs. This not only led to the most efficient known algorithms for such fundamental problems as matching, flow, shortest paths and branchings, but also to a deep understanding of the structure underlying these problems.
This naturally raises the question of obtaining combinatorial algorithms for solving nonlinear programs. A step in this direction was recently taken by N. Devanur, et al., who gave a combinatorial polynomial time algorithm for computing an equilibrium for the linear case of Fisher's market equilibrium model described by W. C. Brainard and H. E. Scarf. N. Devanur, et al. appears to be the first combinatorial algorithm for exactly solving a nonlinear program—the Eisenberg and Gale convex program, which gives, as its optimal solution, equilibrium allocations for this model.
In retrospect, the Eisenberg and Gale convex program was a fine starting point for the question raised above. This remarkable program helps prove, in a very simple manner, basic properties of the set of equilibria: Equilibrium exists under certain (mild) conditions, the set of equilibria is convex, equilibrium utilities and prices are unique, and if the program has all rational entries then equilibrium allocations and prices are also rational. In addition, it also provides a means for characterizing the equilibrium in a combinatorial manner as described by K. Jain, showing that equilibrium utilities satisfy proportional fairness, and approximating it to any specified degree using an ellipsoid algorithm.
The Eisenberg-Gale program maximizes a money weighted geometric mean of buyers' utilities subject to linear packing constraints. What is lacking is a study of combinatorial solvability of several resource allocation markets whose equilibria are captured via convex programs having the same form as the Eisenberg-Gale program. Such algorithms could lead to new insights into the efficiency, fairness, and competition monotonicity of these markets.